#ifndef KBestParseForest_H
#define KBestParseForest_H
#include"ParseForestItem.h"
#include"DependencyInstance.h"
#include"DependencyPipe.h"

class BestPair{
public:
	int first, second;
	BestPair(int first, int second);
	BestPair();
};

class KBestParseForest{
protected:
	vector<string*>* sent;
	vector<string*>* pos;
	int start, end, K;
	
	virtual int getKey(int s, int t, int dir, int comp, int k);
public:
	static int rootType;
	static void setRootType(int i);
	ParseForestItem* chart;
	
	KBestParseForest();
	
	KBestParseForest(int start, int end, DependencyInstance &inst, int K);
	
	virtual ~KBestParseForest();
	
	bool add(int s, int type, int dir, double score);
	
	bool add(int s, int r, int t, int type, int dir, int comp, 
		double score, ParseForestItem* p1, ParseForestItem* p2);
	
	double getProb(int s, int t, int dir, int comp);
	
	double getProb(int s, int t, int dir, int comp, int i);
	
	vector<double>* getProbs(int s, int t, int dir, int comp);
	
	ParseForestItem getItem(int s, int t, int dir, int comp);
	
	ParseForestItem getItem(int s, int t, int dir, int comp, int k);
	
	ParseForestItem* getItems(int s, int t, int dir, int comp);
	
	virtual vector<pair<FeatureVector*, string*> >* getBestParses(DependencyInstance *inst, DependencyPipe *pipe);
	
	virtual vector<pair<FeatureVector*, string*> >* getBestParses(DependencyInstance *inst, DependencyPipe *pipe, vector<vector<vector<double> > > &probs,
		vector<vector<vector<vector<double> > > > &nt_probs, bool labeled);
	
	FeatureVector* getFeatureVector(DependencyInstance *inst, DependencyPipe *pipe, string *depString);
	
	virtual string* getDepString(ParseForestItem &pfi);
	
	vector<BestPair>* getKBestPairs(ParseForestItem *item1, ParseForestItem *item2);
};

class ValueIndexPair{
public:
	double val;
	int i1, i2;
	ValueIndexPair();
	ValueIndexPair(double value, int i1, int i2);
	int compareTo(ValueIndexPair &other);
};

class BinaryHeap{
private:
	int DEFAULT_CAPACITY;
	int currentSize;
	vector<ValueIndexPair> theArray;

	int parent(int i);
	int leftChild(int i);
	int rightChild(int i);
public:
	BinaryHeap(int def_cap);
	ValueIndexPair getMax();
	void add(ValueIndexPair &e);
	ValueIndexPair removeMax();
};
#endif
